package algo.sketch;

import algorithm.AbstractSketch;

public class CountMin extends AbstractSketch{

	public CountMin() {
		super("CountMin");
	}

	public static final long PRIME_MODULUS = (1L << 31) - 1;
	private int depth;
	private int width;
	private long[][] table;
    private double eps;
    private double confidence;
	private long size = 0;
    
    private void init(int d, int w, int nbItem){
    	this.table = new long[d][w];
    }
    
    public void compute(double eps, double confidence, int[] stream){
		this.eps = eps;
		this.confidence = confidence;
		this.depth = (int) Math.ceil(- Math.log(1 - confidence) / Math.log(2));
		this.width = (int) Math.ceil(1 / eps);
		init(depth, width, stream.length);
		
		for(Object item : stream){
			addItem((Integer)item);
		}
	}
	
	private int h(int item, int i){
		long hash = item;
		hash += hash >> 32;
		hash &= PRIME_MODULUS;
		return ((int) hash) % width;
	}
	
	public void addItem(int item){
		for (int j = 0; j < depth; ++j){
			table[j][h(item,j)] += 1;
		}
		size++;
	}

	public double estimateCount(int item){
		double res = Double.MAX_VALUE;
		for (int i = 0; i < depth; ++i){
			res = Math.min(res, table[i][h(item, i)]);
		}
		return res;
	}
	
	public double getRelativeError(){
		return eps;
	}
	
	public double getConfidence(){
		return confidence;
	}
	
	public long getSize(){
		return size; 
	}
}
